/*
 * @ProjectName: 编程学习
 * @Copyright:   2019 HangZhou Yi Dev, Ltd. All Right Reserved.
 * @address:     https://yiyuery.github.io/
 * @date:        2019/10/27 5:32 下午
 * @email:       xiazhaoyang@live.com
 * @description: 本内容仅限于编程技术学习使用，转发请注明出处.
 */
package com.example.algorithm.structure;

import java.util.Stack;

/**
 * <p>
 * 链表实现
 * </p>
 *
 * @author Yi
 * @version V1.0.0
 * @date 2019/10/27 5:32 下午
 * @modificationHistory=========================逻辑或功能性重大变更记录
 * @modify By: {修改人}  2019/10/27
 * @modify reason: {方法名}:{原因}
 * ...
 */
public class LinkedListEx {

    public static void main(String[] args) {
        LinkedNode<Integer> linkedNode = new LinkedNode<Integer>(0);
        LinkedNode<Integer> tempNode = linkedNode;
        int len = 1;
        while (len < 10) {
            tempNode.next = new LinkedNode<>(len);
            tempNode = tempNode.next;
            len++;
        }
        System.out.println("----------> 正向输出链表");
        LinkedListUtil.printLikedElements(linkedNode);
        System.out.println("----------> 逆向输出链表");
        LinkedListUtil.reverse(linkedNode);
        LinkedListUtil.printLikedElements(linkedNode);

    }
}

class LinkedListUtil {

    public static <T> void reverse(LinkedNode<T> head) {
        if (null == head || null == head.next) {
            return;
        }
        LinkedNode<T> currentNode = head;
        Stack<LinkedNode<T>> stack = new Stack<>();
        while (currentNode.next != null) {
            LinkedNode next = currentNode.next;
            //断开链接
            currentNode.next = null;
            stack.push(next);
            currentNode = next;
        }
        head = stack.pop();
        currentNode = head;
        while (!stack.empty()) {
            currentNode.next = stack.pop();
            currentNode = currentNode.next;
        }
    }

    public static <T> void printLikedElements(LinkedNode<T> linkedNode) {
        LinkedNode<T> tempNode = linkedNode;
        while (tempNode.next != null) {
            System.out.println(tempNode.val);
            tempNode = tempNode.next;
        }
    }
}

class LinkedNode<T> {

    T val;

    LinkedNode<T> next;

    LinkedNode(T val) {
        this.val = val;
    }
}